/**
      <one line to give the program's name and a brief idea of what it does.>
    Copyright (C) <2011>  <André Mendes de Oliveira Paiva>

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  
 */

package estrutura.matriz;

import estrutura.*;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;

public class MatrizAdjacencia extends EstruturaDados {

    private No[] vertices;
    private Aresta[][] arestas;
    //File file = new File("/arquivo.txt");
    //FileReader reader = new FileReader(new File("saida.txt"));

    public MatrizAdjacencia(String nome, int qtdeNo) {
        super(nome, qtdeNo);
        vertices = new No[this.getQtdeNo()];
        arestas = new Aresta[this.getQtdeNo()][this.getQtdeNo()];
    }
    public MatrizAdjacencia(String nome) {
        this(nome, QTDE_MAX_NO);
    }
    public MatrizAdjacencia(int qtdeNo) {
        this(NOME_ESTRUTURA_ANONIMA, qtdeNo);
    }

    public MatrizAdjacencia() {
        this(NOME_ESTRUTURA_ANONIMA, QTDE_MAX_NO);
    }

    private int obterMaxId()
    {
        int maxId = 0;
        for (No no : vertices)
        {
            if (no == null) break;
            if (no.getId() > maxId) {
                maxId = no.getId();
            }
        }
        return maxId;
    }

    public boolean inserirNo(String valor) {
        boolean ret = false;
        int i;
        /* Procura pelo primeiro idNoice disponivel no vetor */
        for (i = 0; i < vertices.length; i++) {
            /* quando encontrar o idNoice disponível sai do looping */
            if (vertices[i] == null) {
                break;
            }
        }
        /* se chegou até o fim do looping (fim do vetor) e o vetor já atingiu i
        tamnaho máximo, então retorna -1, uma forma de idNoicar que não é
        possível inserir mais nós
         */
        if (i < this.getQtdeNo()) {
            /* Cria o nó e adiciona-o ao vetor de vertices */
            No novoNo = new No(this.obterMaxId()+1, valor);
            vertices[i] = novoNo;
            ret = true;
        }
        return ret;
    }

    /* Obtem um determinado no a partir do ID do Nó */
    public No obterNo(int idNo) {
        No no = null;
        /* verifica se os dois idNoices estão dentro do range do vetor */
        for (int i = 0; i < vertices.length; i++) {
            if (vertices[i].getId() == idNo) {
                no = vertices[i];
                break;
            }
        }
        /* Verifica se a posição do vetor contem um nó válido */
        if (no == null) {
           // System.out.println("O ID [" + idNo + "] nao existe.");
        }
        return no;
    }

    /* Obtem o índice de um determinado no a partir do ID do Nó */
    public int obterIndiceNo(int idNo) {
        int i;
        /* verifica se os dois idNoices estão dentro do range do vetor */
        for (i = 0; i < vertices.length; i++) {
            if (vertices[i] != null && vertices[i].getId() == idNo) {
                break;
            }
        }
        /* Verifica se a posição do vetor contem um indice válido */
        if (i == vertices.length) {
            //System.out.println("O ID [" + idNo + "] nao existe.");
        }
        return i;
    }

    public Aresta obterAresta(int idNoOrigem, int idNoDestino) {
        Aresta aresta = null;
        int indNoOrigem = this.obterIndiceNo(idNoOrigem);
        int indNoDestino = this.obterIndiceNo(idNoDestino);
        if (indNoOrigem != vertices.length && indNoDestino != vertices.length && arestas[indNoOrigem][indNoDestino] != null) {
            aresta = arestas[indNoOrigem][indNoDestino];
        }
        return aresta;
    }

    public boolean inserirAresta(int idNoOrigem, int idNoDestino) {
        return inserirAresta(idNoOrigem, idNoDestino, null);
    }

    public boolean inserirAresta(int idNoOrigem, int idNoDestino, Object rotulo) {
        return inserirAresta(idNoOrigem, idNoDestino, rotulo, 0);
    }

    public boolean inserirAresta(int idNoOrigem, int idNoDestino, Object rotulo, int peso) {
        boolean ret = false;
        /* verifia se existe aresta */
        if (this.obterAresta(idNoOrigem, idNoDestino) == null) {
            int indOrigem = this.obterIndiceNo(idNoOrigem);
            int indNoDestino = this.obterIndiceNo(idNoDestino);
            if (indOrigem != -1 && indNoDestino != -1) {
                Aresta aresta = new Aresta(rotulo, peso);
                arestas[indOrigem][indNoDestino] = aresta;
                ret = true;
            }
        }
        return ret;
    }

    public boolean inserirRotulo(int idNoOrigem, int idNoDestino, Object rotulo) {
        boolean ret = false;
        Aresta aresta = this.obterAresta(idNoOrigem, idNoDestino);
        if (aresta != null) {
            if (aresta.getRotulo() == null) {
                aresta.setRotulo(rotulo);
                ret = true;
            } else {
                System.out.println("Rotulo ja cadastrado para a aresta!");
            }
        }
        return ret;
    }

    public boolean excluirNo(int idNo) {
        boolean ret = false;
        int ind = this.obterIndiceNo(idNo);
        if (ind != vertices.length) {
            ret = true;
            /* primeiro exclui arestas do nó */
            for (int j = 0; j < arestas[ind].length; j++) {
                arestas[ind][j] = null;
            }
            /* exclui as Arestas dos outros nós que tenham ligação com este nó  */
            for (int i = 0; i < arestas.length; i++) {
                arestas[i][ind] = null;
            }
            /* exclui o nó */
            vertices[ind] = null;
        }
        return ret;
    }

    public boolean excluirRotulo(int idNoOrigem, int idNoDestino) {
        /* verifica se existe aresta */
        boolean ret = false;
        Aresta aresta = this.obterAresta(idNoOrigem, idNoDestino);
        if (aresta != null) {
            aresta.setRotulo(null);
            ret = true;
        }
        else 
        {  
           //System.out.println("Rotulo [" + idNoOrigem + ", " + idNoDestino + "] não existe.");
        }
        return ret;
    }

    public boolean excluirAresta(int idNoOrigem, int idNoDestino) {
        /* verifica se existe aresta */
        boolean ret = true;
        int indNoOrigem = this.obterIndiceNo(idNoOrigem);
        int indNoDestino = this.obterIndiceNo(idNoDestino);
        if (indNoOrigem != vertices.length && indNoDestino != vertices.length && arestas[indNoOrigem][indNoDestino] != null)
            arestas[indNoOrigem][indNoDestino] = null;
        else{
              ret = false;
              //System.out.println("Aresta [" + idNoOrigem + ", " + idNoDestino+ "] não existe.");
        }
        return ret;
    }
    public boolean excluirTodasArestas(int idNo) {
        /* verifica se existe aresta */
        boolean ret = false;
        int ind = this.obterIndiceNo(idNo);
        for (int i = 0; i < arestas[ind].length; i++) {
           if (arestas[ind][i] != null){
            arestas[ind][i] = null;
             ret = true;
           }
        }
        return ret;
    }
    @Override
    public void imprimir() {
        int i;
        super.imprimir();
        for (i = 0; i < vertices.length; i++) {
            if (vertices[i] != null) {
                vertices[i].imprimir();
                System.out.println("Arestas: ");
                for (int j = 0; j < arestas[i].length; j++) {
                    if (arestas[i][j] != null) {
                        if (vertices[j] != null) {
                            if (arestas[i][j].getRotulo() != null)
                               System.out.println("   Valor: " + vertices[j].getValor() + " - " + arestas[i][j].getRotulo().toString());
                            else
                               System.out.println("   Valor: " + vertices[j].getValor());
                        }
                    }
                }
            }
        }
    }

    public void imprimirNosVizinhos(int id) {
        int i = this.obterIndiceNo(id);
        if (i != -1 && vertices[i] != null) {
                vertices[i].imprimir();
                System.out.println("Arestas: ");
                for (int j = 0; j < arestas[i].length; j++) {
                    if (arestas[i][j] != null) {
                        if (vertices[j] != null) {
                           System.out.println("   Valor: " + vertices[j].getValor() + (arestas[i][j].getRotulo() != null ? " - Rotulo: " + arestas[i][j].getRotulo().toString() : ""));
                        }
                    }
                }
        }
    }
    /* Retorna o id da primeira Aresta encontrada ou -1 senão existir aresta*/
    public int obterIDPrimeiraAresta(int idNo) {
        int id = -1;
        int indOrigem = this.obterIndiceNo(idNo);
        if (indOrigem != -1)
        {
          for (int j = 0; j < arestas[indOrigem].length; j++)
          {
             if (arestas[indOrigem][j] != null && vertices[j] != null){
                 id = vertices[j].getId();
                 break;
              }
          }
        }
        return id;
    }

    /* Retorna o id da próxima Aresta encontrada ou -1 senão existir aresta*/
    public int obterIDProximaAresta(int idNoOrigem, int idNoDestino) {
        int id = -1;
        int indOrigem  = this.obterIndiceNo(idNoOrigem);
        int indDestino = this.obterIndiceNo(idNoDestino);
        if (indOrigem != -1 && indDestino != -1)
        {
          for (int j = 0; j < arestas[indOrigem].length; j++)
          {
             if (arestas[indOrigem][j] != null && vertices[j] != null && vertices[j].getId() != idNoDestino){
                 id = vertices[j].getId();
                 break;
              }
          }
        }
        return id;
    }

    /* Retorna o rotulo da ligação ou null senão não existir aresta*/
    public Object obterRotuloAresta(int idNoOrigem, int idNoDestino) {
        Aresta aresta = this.obterAresta(idNoOrigem, idNoDestino);
        if (aresta != null && aresta.getRotulo() != null) {
            return aresta.getRotulo();
        }
        return null;
    }
    
    /* Obtem o ID de um determinado no a partir do valor Nó */
    public int obterIdPorValor(String valor)
    {
       int i = -1;
        /* Pesquisa o Valor do Nó */
        for (i = 0; i < vertices.length; i++) {
            if (vertices[i].getValor().equals(valor)) {
                i = vertices[i].getId();
                break;
            }
        }
        return i;
    }
    public boolean obterDadosArquivo(String arquivo)
    {
        boolean res = true;
        String linha;
        try
        {
          FileReader      fr = new FileReader(arquivo);
          BufferedReader  br = new BufferedReader(fr);
          String []nos;      /* vetor de nós, obtido a partir da 1ª linha do arquivo */
          String []arestasArq;  /* vetor de arestas, obtido a partir da 2ª linha do arquivo */
          /* Lê a primeira linha, contendo os nós */
          linha = br.readLine();
          if (linha != null)
          {
            nos =  linha.split(";");
            /* insere os nós */
            for(int i = 0; i < nos.length; i++)
            {
                if (!(nos[i].trim()).equals(""))
                  this.inserirNo(nos[i]);
            }
          }
          int indNoOrigem;
          /* Lê as arestas e inclui as mesmas no grafo */
          while ((linha = br.readLine()) != null)
          {
             arestasArq = linha.split(";");
             /* obtem o ID do nó de origem, a partir do valor do nó */
             indNoOrigem = (this.obterIdPorValor(arestasArq[0]));
             if (indNoOrigem != -1)
             {
                for(int i = 1; i < arestasArq.length; i++)
                {
                   /* Se o valor for 1, então é para criar a aresta */
                    if ((arestasArq[i].trim()).equals("1.0"))
                      this.inserirAresta(indNoOrigem, i);
                }
             }
          }
        }
        catch (Exception e)
        {
           System.out.println("Erro ao obter os dados do arquivo: " + e.getMessage());
           res = false;
        }
       return res;
    }
    public boolean gerarArquivoEstrutura(String arquivo)
    {
        boolean res = true;
        String linha="";
        try
        {
          FileWriter      fr = new FileWriter(arquivo);
          BufferedWriter  br = new BufferedWriter(fr);
          int indUltNo = -1;
          /* Lê os nós */
          for (int i = 0; i < vertices.length; i++ )
          {
             if (vertices[i] != null){
               indUltNo = i;
               linha += ";" + vertices[i].getValor();
              }
          }
          /* grava a primeira linha do arquivo com os nós */
          br.write(linha);
          No no;
          /* Lê né e verifica as conexões do mesmo */
          for (int i = 0; i < vertices.length; i++ )
          {
            if (vertices[i] != null)
            {
                no = vertices[i];
                linha = no.getValor();
                for (int j = 0; j <= indUltNo; j++ )
                {
                   if ( arestas[i][j] != null)
                     linha += ";" + "1.0";
                   else
                     linha += ";" + "0";
                }
                /* grava linha de arestas do nó */
                br.write("\n");
                br.write(linha);
           }
          }
         br.close();
        }
        catch (Exception e)
        {
           System.out.println("Erro ao gravar os dados no arquivo: " + e.getMessage());
           res = false;
        }
       return res;
    }

    /* Obtem o Id do nó Origem, ou seja o nó que não é destino de nenhum outro nó */
    public int obterIDNoOrigem()
    {
       int i, j, id = -1;
       boolean achou ;
       for (i = 0; i < this.vertices.length; i++)
       {
         achou = false;
         for (j = 0; j < this.arestas[i].length; j++)
         {
           /* Verifica se o Nó na posição i faz parte de alguma aresta como nó destino */
           if (arestas[j][i] != null){
              achou = true;
              break;
           }
         }
         if (!achou)
         {
            id = vertices[i].getId();
            break;
         }
       }
       return id;
    }
    /* Obtem o Id do nó Destino, ou seja o nó que não é Origem de nenhum outro nó */
    public int obterIDNoDestino()
    {
       int i, j, id = -1;
       boolean achou ;
       for (i = 0; i < this.vertices.length; i++)
       {
         achou = false;
         for (j = 0; j < this.arestas[i].length; j++)
         {
           /* Verifica se o Nó na posição i faz parte de alguma aresta como nó origem */
           if (arestas[i][j] != null){
              achou = true;
              break;
           }
         }
         if (!achou)
         {
            id = vertices[i].getId();
            break;
         }
       }
       return id;
    }

    public ArrayList<No> obterVertices() {
        ArrayList <No> listaNo = new ArrayList<No>();
        for(int i = 0; i < vertices.length; i++)
            if (vertices[i] != null)
               listaNo.add(vertices[i]);
       return listaNo;
    }

    public ArrayList<No> obterNosVizinhos(int idNo)
    {
        ArrayList <No> listaNo = new ArrayList<No>();
        int ind = this.obterIndiceNo(idNo);
        if (ind != -1)
        {
           for (int j = 0; j < arestas[ind].length; j++)
             if (arestas[ind][j] != null){
                 listaNo.add(vertices[j]);
               }
        }
        return listaNo;
    }
    public No obterNoPorID(int idNo)
    {
       return this.obterNo(idNo);
    }
}
